
//编程查找两个字符串中最大的公共子串

#include <iostream>
#include <cstring>
using namespace std;

/**
    遍历长度较短的字符串的所有子串是否在另一个字符串中

    例如：str1 = abcdefg ; str2 = cdeab
        注意：str2子串分解由大到小，长度为5的子串，长度为4的子串，长度为3的子串。
    1. 先查找长度为5的子串是否存在str1中
    2. 查找长度为4的子串是否在str1中
    ....
    上述操作可以通过strstr(str1,stri)!=NULL,则存在，==NULL则不存在
    分解方式：
        cdeab --> cdea,deab --> cde,dea,eab--> cd,de,ea,ab-->c,d,e,a,b
        实际上，就是给一个框，移动这个框，比如框大小为5，一下就框住了cdeab
        如果框大小为4，那么首先框住cdea，向后移动一个元素，框住了deab，不能再向后移动了
        如果框大小为3，那么可以移动三次
        每次移动判断框的尾部是否=len-1
*/

char * getMaxSub(char * str1,char *str2)
{
    char * longStr,* shortStr,* subStr;
    longStr = strlen(str1)>strlen(str2)?str1:str2;
    shortStr = strlen(str1)>strlen(str2)?str2:str1;

    if(strstr(longStr,shortStr)!=NULL)
    {
        return shortStr;
    }
    subStr = (char *)malloc(strlen(shortStr)*sizeof(char));
    for(int i=strlen(shortStr);i>=1;i--)
    {
        //拷贝子串
        int box = i-1;
        for(int j=0;j<=(strlen(shortStr)-box);j++)
        {
            subStr = strncpy(subStr,&shortStr[j],box);
            subStr[box]='\0';
            if(strstr(longStr,subStr)!=NULL)
            {
                return subStr;
            }
        }

    }
    //没找到公共子串
    free(subStr);
    subStr=NULL;
    return NULL;
}

int main()
{

    //查找子串的函数
    char *str1 = "abcdefg";
    char *str2 = "cdeab";
    char * maxSub = getMaxSub(str1,str2);
    cout<<"最大公共子串："<<maxSub<<endl;
    system("pause");
    return 0;
}
